//
//  BubbleSort.swift
//  数据结构
//
//  Created by Fearless on 2020/10/10.
//  Copyright © 2020 XFB. All rights reserved.
//

import Foundation

class BubbleSort {

    var sortArray:[Int] = []
    
    init(array:[Int]) {
        sortArray = array
    }
    
    func sort() {
        
        guard sortArray.count > 0 else {
            return
        }

        let count = sortArray.count
        // 遍历的次数
        for i in 0 ..< count-1 {
            // 遍历一次，最后一个数字最大不需要再次遍历，需要减去i
            for j in 0 ..< count-1-i {
                // 如果前一个元素 比 后一个元素大，交换位置
                if sortArray[j] > sortArray[j+1] {
                    // 简化
                    sortArray.swapAt(j, j + 1)
//                    let temp = sortArray[j];
//                    sortArray[j] = sortArray[j+1];
//                    sortArray[j+1] = temp;
                }
            }
        }
//        print(sortArray)
    }
    
    
    // 增加标志位
    func sort1() {
        guard sortArray.count > 0 else {
            return
        }
        for i in 0 ..< sortArray.count-1 {
            var flag = true
            for j in 0 ..< sortArray.count-1-i {
                if sortArray[j] > sortArray[j + 1] {
                    sortArray.swapAt(j, j + 1)
                    // 发生交换，标志位为false
                    flag = false
                }
            }
            // 如果没有交换，就已经是有序的
            if flag == true {
                break
            }
        }
//        print(sortArray)
    }
 
    // 优化2 增加索引标记
    func sort2() {
        guard sortArray.count > 0 else {
            return
        }
        
        let count = sortArray.count
        for var i in 0 ..< count-1 {
            var sortedIndex = 0
            for j in 0 ..< count-1-i {
                if sortArray[j] > sortArray[j + 1] {
                    let temp = sortArray[j];
                    sortArray[j] = sortArray[j + 1]
                    sortArray[j + 1] = temp
                    sortedIndex = j;
                }
            }
            i = sortedIndex + 1
        }
//        print(sortArray)

    }
}
